/*
 * @lc app=leetcode.cn id=1109 lang=typescript
 *
 * [1109] 航班预订统计
 */

// @lc code=start

//  思想：差分数组
//  参考：https://mp.weixin.qq.com/s/9L6lz0XDZ9gi-d_iPrSs8Q

//  复杂度：O(n) O(n)

function corpFlightBookings(bookings: number[][], n: number): number[] {
    const nums = new Array(n).fill(0)
    const df = new Difference(nums)

    for (const booking of bookings) {
        // 从 1 开始
        const i = booking[0] - 1
        const j = booking[1] - 1
        const val = booking[2]
        df.increment(i, j, val)
    }

    return df.result()
};

class Difference {
    diff: number[]
    constructor(nums: number[]) {
        this.diff = new Array(nums.length)
        this.diff[0] = nums[0]
        for (let i = 1; i < nums.length; i++) {
            this.diff[i] = nums[i] - nums[i - 1]
        }
    }
    increment(i: number, j: number, val: number) {
        this.diff[i] += val
        if (j + 1 < this.diff.length) {
            this.diff[j + 1] -= val
        }
    }
    result(): number[] {
        const res = new Array(this.diff.length)
        // 根据差分数组构造结果数组
        res[0] = this.diff[0]
        for (let i = 1; i < this.diff.length; i++) {
            res[i] = res[i - 1] + this.diff[i]
        }
        return res
    }
}
// @lc code=end

console.log(corpFlightBookings([[1, 2, 10], [2, 3, 20], [2, 5, 25]], 5))
